1. Field of the Invention
The present invention relates to the generation of cryptographically secure sequences at very high speed. More particularly, this invention relates to the generation of such sequences with predetermined probability distribution with cryptographic security based on zeta-one-way functions with applications to authentication, key transfer, and public-key cryptography.
2. Description of the Prior Art
In 1917 Gilbert Vernam introduced the one-time pad cryptosystem, a secret key cryptosystem for telegraphic communication (D. Kahn, The codebreakers: the story of secret writing, Macmillan, New York, N.Y. (1967), 394-396). The one-time pad cryptosystem is provably secure from the information-theoretic point of view introduced by Claude Shannon (C. E. Shannon, Communication theory of secrecy systems, Bell Systems Technical Journal 28 (1949), 657-715) and later refined by Martin Hellman (M. E. Hellman, An extension of Shannon's approach to cryptography, IEEE Transaction on Information Theory v. IT-23 n.3 (1977), 289-294). The one-time pad system, according to Ronald Rivest, in his survey of contemporary cryptography, is rarely used because of the difficulty in generating, sharing, and storing very large keys (R. L. Rivest, Cryptography, p.721 in Handbook of theoretical computer science volume A: Algorithms and complexity, J. Van Lueewen, managing editor, MIT Press, Cambridge, Mass. (1994)). Rivest points out that one motivation for generating random pseudorandom sequences is for use in the one-time pad cryptosystem (ibid p. 735). According to Rivest (ibid p. 737) Manuel Blum and Silvio Micali introduced the first method for designing provably secure pseudorandom bit generators based on one-way predicates (M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, vol. 13 no. 4 (1984). The term cryptographically secure in this setting is from the perspective of computational complexity. Rivest (ibid p. 738) also notes that a perfect pseudorandom bit generator exists if and only if there exists a one-way function F that cannot be easily inverted at points G(x) where G is the t.sup.th iterate of F applied to a k-bit string x. Rivest attributes this result to Leonid Levin (L. A. Levin, One-way functions and pseudorandom number generators, Combinatorica 7 (1987), 357-363).
According to Rivest (ibid p. 729), the notion of a public-key system was first published by Whitfield Diffie and Martin Hellman in 1976 (W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory IT-22 (1976), 644-654, also described in U.S. Pat. No. 4,200,700). Rivest observes that their general method makes use of trapdoor one-way permutations (ibid p. 729). Rivest also observes that the Diffie-Hellman method allows two parties to establish a shared secret key via a public discussion that anyone can overhear. Rivest himself, together with Adi Shamir and Leonard Adleman, introduced a system known today as the RSA public-key cryptosystem (R. Rivest, A. Shamir, and L. M. ADLEMAN, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21 (1978), 120-126, also described in U.S. Pat. No. 4,405,829). The pioneering work on probabilistic public-key encryption was performed by Shafi Goldwasser and Silvio Micali (S. Goldwasser and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences 26 (2) (1984), 270-299). Goldwasser and Micali employ the intractability of the quadratic residue problem in their constructions. The Diffie-Hellman, the RSA and the Goldwasser and Micali systems employ trapdoor one-way functions which have the deficiency that they require non-linear computations in extremely large finite rings.
The idea of a zeta one-way function was announced at the Special Session on Analytical Number Theory, Spring Meeting of the American Mathematical Society, Polytechnic University, Brooklyn, N.Y., Apr. 9, 1994 (M. Anshel and D. Goldfeld, Zeta functions as one-way functions and cryptography, A.M.S. Abstracts, Vol 15, no. 3 (April 1994), p. 349). Examples of such one-way functions are implicit in the earlier literature. For example, Kevin McCurley, in reference to sequences that are hard to predict (Kevin S. McCurley, Odds and ends from cryptology and computational number theory, in Cryptology and Computational Number Theory, C. Pomerance, Editor of the Proceedings of the Symposia in Applied Mathematics, Volume 42, A.M.S. Providence, R.I. (1990), p. 162) cites the work of Ivan Bjerre Damg.ang.rd (I. V. Damg.ang.rd, On the randomness of Legendre and Jacobi sequences, in Advances in Cryptology (Proceedings of Crypto '88), Lecture Notes in Computer Science, Springer-Verlag 403 Berlin (1990), 163-172). Damg.ang.rd employs Legendre and Jacobi sequences to produce sequences which are difficult to predict. Leonard Adleman and Kevin McCurley draw on Legendre sequences to define and discuss the Quadratic Signature Problem in connection with the complexity of factoring and its relation to the extended Riemann hypothesis (Leonard M. Adleman and Kevin S. McCurley, Open problems in number theoretic complexity II, in Algorithmic Number Theory, Leonard M. Adleman and Ming-Deh Huang (Editors), Lecture Notes in Computer Science 877 Berlin (1994), 301-302). The current invention utilizes the unpredictability of certain Jacobi sequences and a generalization of the Quadratic Signature Problem to construct new trapdoor functions from zeta one-way functions for applications to private and public key cryptography.